/*
 * hash_map.c
 *
 *  Created on: 2012-8-6
 *      Author: lin
 */

#include "hash_map.h"
#include "util/util_number.h"

#define Map hash_map_t
#define Entry hash_map_entry_t
#define HASH_MAP_MAX_CAPACITY INT32_MAX

static inline void _add_entry(Entry** table, Entry* e, uint32_t idx) {
    e->next = table[idx];
    table[idx] = e;
}

static inline Entry* _find_entry(uint32_t idx, Entry** table,
        mixed_t_compare_fn* key_cmp_fn, uint32_t hashcode, mixed_t key,
        Entry** prev) {
    Entry *eprev = NULL;
    for (Entry *e = table[idx]; e; eprev = e, e = e->next) {
        if (e->hash == hashcode && key_cmp_fn(e->key, key) == 0) {
            if (prev) {
                *prev = eprev;
            }
            return e;
        }
    }
    return NULL;
}
Map* hash_map_new0(uint32_t capacity, float factor) {
    assert(factor > 0 && factor <= 1);
    uint32_t pc = number_next_power(capacity,DEF_HASH_MAP_CAPACITY,HASH_MAP_MAX_CAPACITY);
    Entry ** table = zcalloc(sizeof(Entry*) * pc);
    Map* map = zcalloc(sizeof(Map));
    map->capacity = pc--;
    map->capacity_mask = pc;
    map->size = 0;
    map->table = table;
    map->factor = factor;
    map->thresold = (uint32_t)(map->capacity * factor);
    return map;
}
void hash_map_clean(Map* hmap) {
    uint32_t size = hmap->size;
    uint32_t capacity = hmap->capacity;
    Entry** table = hmap->table;

    mixed_t_free_fn key_free_fn = hmap->key_free_fn;
    mixed_t_free_fn val_free_fn = hmap->val_free_fn;

    for (uint32_t i = 0; i < capacity && size > 0; i++) {
        Entry *e, *nexte;
        e = table[i];
        while (e) {
            nexte = e->next;
            mixed_t_free(key_free_fn, e->key);
            mixed_t_free(val_free_fn, e->val);
            zfree(e);
            e = nexte;
            --size;
        }
    }
    hmap->size = 0;
}

void hash_map_rehash(Map* hmap, uint32_t newcapacity) {
    newcapacity = number_next_power(newcapacity,DEF_HASH_MAP_CAPACITY,HASH_MAP_MAX_CAPACITY);

    uint32_t capacity = hmap->capacity;
    uint32_t size = hmap->size;

    if (capacity == newcapacity || size == 0) {
        return;
    }
    Entry** table = hmap->table;
    Entry** newtable = zcalloc(sizeof(Entry*) * newcapacity);
    uint32_t mask = newcapacity - 1;
    for (uint32_t i = 0; i < capacity && size > 0; i++) {
        Entry *e = table[i];
        Entry* next;
        while (e) {
            next = e->next;
            uint32_t idx = e->hash & mask;
            _add_entry(newtable, e, idx);
            e = next;
            --size;
        }
    }
    zfree(hmap->table);
    hmap->table = newtable;
    hmap->capacity = newcapacity;
    hmap->capacity_mask = mask;
    hmap->thresold = newcapacity * hmap->factor;

}

static inline Entry* _map_add(Map* hmap, mixed_t key, mixed_t val) {
    Entry** table = hmap->table;
    uint32_t hashcode = hmap->key_hash_fn(key);
    uint32_t idx = hashcode & hmap->capacity_mask;
    Entry* e = _find_entry(idx, table, hmap->key_compare_fn, hashcode, key,
            NULL);
    if (e) {
        return e;
    }

    e = zmalloc(sizeof(Entry));
    e->hash = hashcode;
    e->key = key;
    e->val = val;
    _add_entry(table, e, idx);
    if (++hmap->size > hmap->factor) {
        hash_map_rehash(hmap, hmap->capacity >> 1);
    }
    return NULL;
}
int hash_map_put_absent(Map* hmap, mixed_t key, mixed_t val) {
    Entry* e = _map_add(hmap, key, val);
    return e ? HASH_MAP_EXIST : HASH_MAP_ABSENT;
}
int hash_map_put(Map* hmap, mixed_t key, mixed_t val) {
    Entry* e = _map_add(hmap, key, val);
    if (!e) {
        //not exist
        return HASH_MAP_ABSENT;
    }
    Entry** table = hmap->table;
    uint32_t hashcode = hmap->key_hash_fn(key);
    uint32_t idx = hashcode & hmap->capacity_mask;
    Entry* e = _find_entry(idx, table, hmap->key_compare_fn, hashcode, key,
            NULL);
    mixed_t dupto = val;
    mixed_t_dup_fn dup_fn = hmap->val_dup_fn;
    if (dup_fn && dup_fn(val, &dupto)) {
        return HASH_MAP_ERR;
    }
    mixed_t_free(hmap->val_free_fn, e->val);
    e->val = dupto;
    return HASH_MAP_EXIST;
}

static int _map_remove(Map* hmap, mixed_t key, int nofree) {
    Entry** table = hmap->table;
    uint32_t hashcode = hmap->key_hash_fn(key);
    uint32_t idx = hashcode & hmap->capacity_mask;
    Entry** prev;
    Entry* e = _find_entry(idx, table, hmap->key_compare_fn, hashcode, key,
            prev);
    if (!e) {
        return HASH_MAP_ABSENT;
    }
    if (*prev != NULL) {
        **prev->next = e->next;
    } else {
        table[idx] = e->next;
    }

    if (!nofree) {
        mixed_t_free(hmap->key_free_fn, e->key);
        mixed_t_free(hmap->val_free_fn, e->val);
    }

    zfree(e);
    --hmap->size;
    return HASH_MAP_EXIST;

}
int hash_map_remove(Map* hmap, mixed_t key) {
    return _map_remove(hmap, key, 0);
}
int hash_map_remove_nofree(Map* hmap, mixed_t key) {
    return _map_remove(hmap, key, 1);
}

int hash_map_get_hash(Map* hmap, mixed_t key, uint32_t keyhash,mixed_t* val) {
    uint32_t idx= keyhash&hmap->capacity_mask;
    Entry* e = _find_entry(idx, hmap->table, hmap->key_compare_fn, keyhash, key,
            NULL);
    if (!e) {
        return HASH_MAP_ABSENT;
    }
    *val = e->val;
    return HASH_MAP_EXIST;
}

Entry* hash_map_begin(Map *hmap) {
    uint32_t size = hmap->size;
    if (size == 0) {
        return NULL;
    }
    uint32_t capacity = hmap->capacity;
    Entry **table = hmap->table;
    for (uint32_t i = 0; i < capacity; i++) {
        if (table[i]) {
            return table[i];
        }
    }
    return NULL;
}
Entry* hash_map_next(Map *hmap, Entry* cur) {
    if (cur->next) {
        return cur->next;
    }
    uint32_t idx = cur->hash & hmap->capacity_mask;
    uint32_t capacity = hmap->capacity;
    Entry **table = hmap->table;
    for (uint32_t i = idx + 1; i < capacity; i++) {
        if (table[i]) {
            return table[i];
        }
    }
    return NULL;
}

#undef Map
#undef Entry
